// 插入排序
/*
    插入排序算法思想：每次将一个待排序的记录按其关键字大小插入到前面(后面)已排好序的子序列中，直到全部记录插入完成。

其中插入排序分为两种：
    直接插入排序：顺序查找找到插入位置，适用于顺序表、链表
    折半插入排序：这般查找找到插入位置，仅适用于顺序表【注意:一直到low > high才停止查找。当mid所指元素等于当前元素时，为保证算法的稳定性，应继续令low = mid+1.最终应将当前元素插入到low所指位置(即high+1)】
*/
/*
    稳定
    平均时间复杂度O(n^2)，最好时间复杂度O(n)，最坏时间复杂度O(n^2);
    空间复杂度O(1);
*/

#include <iostream>

using namespace std;

void InsertSort(int A[], int n) // 利用直接插入排序对数组A进行升序(从小到大)排序
{
    int i, j, temp;         // temp:插入操作的暂存单元
    for (i = 1; i < n; ++i) // 依次将A[2]~A[n]插入到前面已排好序的序列
    {
        if (A[i] < A[i - 1]) // 若A[i]关键字小于前驱，则需要使A[i]不断向前移动直至A[i]大于等于前驱
        {
            temp = A[i];                                // 用temp暂存A[i]
            for (j = i - 1; j >= 0 && A[j] > temp; --j) // 检查所有前面已排好序的元素
                A[j + 1] = A[j];                        // 所有大于temp的元素都向后挪位，空出A[i]的插入位置
            A[j + 1] = temp;                            // 把temp(A[i])插入到大于等于前驱的位置上
        }
    }
    return;
}

void BSInsertSort(int A[], int n) // 折半插入排序(升序)[即寻找A[i]的插入位置时用折半查找]
{
    int i, j, temp, low, high, mid;
    for (i = 1; i < n; ++i) // 依次将A[1]~A[n-1]插入到前面已排好序的序列
    {
        temp = A[i]; // 将A[i]暂存到temp
        low = 0;
        high = i - 1;       // 设置折半查找的范围
        while (low <= high) // 折半查找(默认递增有序)
        {
            mid = (low + high) / 2; // 取中间点
            if (temp < A[mid])      // 查找左半子表
                high = mid - 1;
            else // 查找右半子表
                low = mid + 1;
        }
        for (j = i - 1; j > high; --j) // 将大于A[i]的元素后移，空出插入位置
            A[j + 1] = A[j];
        A[high + 1] = temp; // 将temp(A[i])插入
    }
}

// 测试代码
int main()
{
    int A[100] = {2, 4, 3, 7, 9, 1, 6, 5, 8};
    // InsertSort(A, 9);
    BSInsertSort(A, 9);

    for (int i = 0; i < 9; ++i)
        cout << A[i] << ' ';
    return 0;
}